BZOJ5343【CTSC2018】混合果汁 <整体二分+线段树>

Problem

【CTSC2018】混合果汁

Description

热衷于做黑暗料理，尤其是混合果汁。
商店里有种果汁，编号为。号果汁的美味度是每升价格为。在制作混合果汁时，还有一些特殊的规定，即在一瓶混合果汁中，号果汁最多只能添加升。
现在有个小朋友过来找要混合果汁喝，他们都希望用商店里的果汁制作成一瓶混合果汁。其中，第个小朋友希望他得到的混合果汁总价格不大于，体积不小于。
在上述这些限制条件下，小朋友们还希望混合果汁的美味度尽可能地高，一瓶混合果汁的美味度等于所有参与混合的果汁的美味度的最小值。请你计算每个小朋友能喝到的最美味的混合果汁的美味度。

Input

输入第一行包含两个正整数，表示果汁的种数和小朋友的数量。接下来行，每行三个正整数，表示号果汁的美味度为，每升价格为，在一瓶果汁中的添加上限为。
接下来行依次描述所有小朋友：每行两个数正整数描述一个小朋友，表示他最多能支付元钱，他想要至少升果汁。

Output

对于每个小朋友，输出一行，包含一个整数，表示他能喝到的最美味的混合果汁的美味度。如果无法满足他的需求，则输出。

Sample Input

Sample Output

HINT

对于所有的测试数据，保证，，。

测试点编号			其他限制
			无
			无
			无


			无

标签：整体二分 线段树

Solution

整体二分常规题，考场上居然没做起签到题

考虑对每个询问二分答案，对于当前答案，将所有美味度大于等于的果汁提出来，从花费小的往花费大的贪心选判断钱是否够即可。这样复杂度是。
优化方式有两种：

二分判断用主席树优化。首先将所有果汁按美味度从大到小排序并构建以值为下标的值域线段树，存储的信息为价格在当前区间内的所有果汁的总体积以及总价格。在主席树上二分即可找到最小花费，这样复杂度为，总复杂度
对所有询问进行整体二分，中间用值域线段树维护。整体二分过程需要支持动态插入一种果汁，在线段树上二分得到最小花费。总复杂度。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
#define mid ((s+t)>>1)
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, m, sz, val[MAX_N+5], ans[MAX_N+5];
struct juice {int d, p, v;} a[MAX_N+5];
struct query {int id; lnt w, v;} q[MAX_N+5], tq[MAX_N+5];
struct node {lnt p, v;} tr[MAX_N<<2]; bool mrk[MAX_N+5];
bool cmpd(const juice &a, const juice &b) {return a.d > b.d;}
bool cmpp(const juice &a, const juice &b) {return a.p < b.p;}
void update(int v) {
    tr[v].p = tr[v<<1].p+tr[v<<1|1].p;
    tr[v].v = tr[v<<1].v+tr[v<<1|1].v;
}
void modify(int v, int s, int t, int p, int x) {
    if (s == t) {tr[v].p += 1LL*p*x, tr[v].v += x; return;}
    if (p <= mid) modify(v<<1, s, mid, p, x), update(v);
    else modify(v<<1|1, mid+1, t, p, x), update(v);
}
lnt query(int v, int s, int t, lnt x) {
    if (s == t) return 1LL*s*x;
    if (x <= tr[v<<1].v) return query(v<<1, s, mid, x);
    return tr[v<<1].p+query(v<<1|1, mid+1, t, x-tr[v<<1].v);
}
void bi_solve(int l, int r, int s, int t) {
    if (s > t) return;
    if (s == t) {
        for (int i = l; i <= r; i++)
            ans[q[i].id] = a[s].d;
        return;
    }
    int lsz = 0;
    for (int i = s; i <= mid; i++)
        modify(1, 1, MAX_N, a[i].p, a[i].v);
    for (int i = l; i <= r; i++)
        if (tr[1].v < q[i].v) mrk[i] = false;
        else {
            lnt tot = query(1, 1, MAX_N, q[i].v);
            mrk[i] = q[i].w >= tot, lsz += mrk[i];
        }
    for (int i = l, p1 = l, p2 = l+lsz; i <= r; i++)
        if (mrk[i]) tq[p1++] = q[i]; else tq[p2++] = q[i];
    for (int i = l; i <= r; i++) q[i] = tq[i];
    bi_solve(l+lsz, r, mid+1, t);
    for (int i = s; i <= mid; i++)
        modify(1, 1, MAX_N, a[i].p, -a[i].v);
    bi_solve(l, l+lsz-1, s, mid);
}
int main() {
    read(n), read(m);
    for (int i = 1; i <= n; i++) read(a[i].d), read(a[i].p), read(a[i].v);
    for (int i = 1; i <= m; i++) q[i].id = i, read(q[i].w), read(q[i].v);
    sort(a+1, a+n+1, cmpd), a[n+1].d = -1; bi_solve(1, m, 1, n+1);
    for (int i = 1; i <= m; i++) printf("%d\n", ans[i]); return 0;
}